package com.mc.algorithm;
import java.util.Map;
import java.util.HashMap;
public class ThirtyEight {
	public static int count(int[] array, int key){
		
		Map<Integer,Integer> map = new HashMap<Integer,Integer>();
		for(int i=0;i<array.length;i++){
			if(map.containsKey(array[i]))
				map.put(array[i], map.get(array[i])+1);
			else
				map.put(array[i], 1);
		}
		return map.get(key);
	}
	public static int countBS(int[] array, int key){
		int low =0;
		int high = array.length;
		int mid = low+(high-low)/2;
		while(array[mid]!=key){
			if(array[mid]>key){
				high = mid-1;
			}
			else{
				low = mid+1;
			}
			mid = low+(high-low)/2;
		}
		int i;
		int count = 1;
		if(mid>0){
			i= mid-1;
			while(array[i]==key){
				i--;
				count++;
			}
		}
		if(mid<array.length-1){
			i = mid+1;
			while(array[i]==key){
				i++;
				count++;
			}
		}

		return count;
	}
	public static void main(String[] args) {
		int res = ThirtyEight.countBS(new int[]{1,2,3,3,3,4}, 1);
		System.out.println(res);
	}
}
